[Coding007] DataStructure
顺序表中元素的删除

Ben 2023/07/27

More coding records
Get the knowledge flowing and circulating! :)

标题：顺序表的基本操作与元素的删除（C语言版）Demo代码（加上了前面2次的代码 · 完整版）运行结果代码整体解释

标题：顺序表的基本操作与元素的删除（C语言版）

本部分操作：
删除目标位置的一个元素
获取目标位置的元素
获取某元素的第一次出现的位置，没有就返回-1

Demo代码（加上了前面2次的代码 · 完整版）


xxxxxxxxxx
263
1
// 顺序表的初始化
2

3
#include"stdio.h"  
4
#include"malloc.h"  // malloc
5

6
#include"stdlib.h"  // exit
7

8
#define List_InitSize 100
9
#define List_Increment 10
10

11
typedef struct{
12
    int *elem;  // 存储空间基址
13
    
14
    int length;  // 当前长度
15
    int listsize; // 当前分配的存储容量(以sizeof(int)为单位)
16
}SqList;
17

18
// 【C段代码】调用示例：
19
// SqList l; 
20
// Init_SqList03(&l);
21
void Init_SqList03(SqList *L)
22
{
23
    L->elem = (int*)malloc(List_InitSize * sizeof(int));
24
    if (!L->elem)
25
    {
26
        exit(-2);
27
    }
28
        
29
    L->length = 0;
30
    L->listsize = List_InitSize;
31
}
32

33
void DestroyList_Sq(SqList *L)
34
{
35
    free(L->elem);      // free((*L).elem);
36
    L->elem = NULL;     // (*L).elem = NULL;  // 置空防止野指针 
37
    L->length = 0;      // (*L).length = 0; 
38
    L->listsize = 0;    // (*L).listsize = 0; 
39
} 
40

41
// 清除 
42
int ClearList_Sq(SqList *L)
43
{
44
    // 直接把L->length置为0即可，这样在下一次插入操作的时候，之前的元素就被覆盖了。（其实，在计算机内部，当你申请了一段内存用于存放元素的时候，这个内存中已经存放了一些随机数。这些随机数会在插入操作时被覆盖。）
45
    L->length = 0;
46
    return 0;
47
}
48

49
/*
50
// 清除顺序表：无返回值版 
51
void ClearList(SqList *L)
52
{
53
    L->length = 0;
54
}
55
*/
56

57
// 求长度 
58
int ListLength_Sq(SqList *L)
59
{
60
    // 直接返回顺序表中元素的长度即可。注意，顺序表的长度和顺序表的容量是两个概念。顺序表的容量是表示这个表能存放多少元素。顺序表的长度表示这个顺序表中已经存在了多少元素。
61
    return L->length;
62
}
63

64
// 判空 
65
int ListIsEmpty_Sq(SqList *L)
66
{
67
    if(L->length == 0)
68
        return 1;
69
    else
70
        return 0;
71
}
72

73
// 画个图，形象地说一下这个问题。 
74
int ListInsert_Sq(SqList *L, int i, int e)
75
{
76
    // 这里的i，要想清楚它的含义。这里的i是指，在第i位之前（i从1开始）。比如，在第0号位插入，就是在第1号位之前插入，即，i=1。 
77
    // * 假设顺序表初始长度为10，目前里面已经有了1个元素。我们可以插入的位置，用计算机语言描述插入位置的下标可以是（0号位，1号位。不能插入2号位，因为是顺序存储，不能跳）
78
    // * 那么，用大众的思维，我们如果要插入0号位。那就是说，在第1个位置之前插入，即i=1。对应的，该位置的地址可以利用语句 [(*L).elem + i - 1]表示。
79
    // * 并且，如果我们要插入在第1号位，在本例中，1号位就是顺序表的最后1个位置的后面。那就是说，在第2个位置插入。那么，2怎么来的呢？
80
    // ** 2应该是当前顺序表内元素的个数+1.换句话说，在最后一位插入，就是在当前顺序表的length + 1位插入。 
81
    // ** 比如，现在顺序表中有3个元素。我想在最后1位之后插入。那就是获取L的length(也就是3),在这个位置后面插入就行了，即i要再增加1位，变为4，因为对应的代码应该延续上面的，有一个减1的操作。 [(*L).elem + 4 - 1]
82
    // * 所以，这里我们要判断的是，待插入位置，不能小于1（大众思维）；不能大于length+1（比如已存3个元素，我们最多在第4个位置插入） 
83
    
84
    if((i < 1) || i > L->length + 1)
85
        return 0;
86
    
87
    if (L->length >= L->listsize)
88
    {
89
        int *newbase = (int*)realloc(L->elem, (L->listsize + List_Increment) * sizeof(int));
90
        if (!newbase)
91
        {
92
            exit(-2);
93
        }
94
        
95
        L->elem = newbase;
96
        L->listsize = L->listsize + List_Increment;
97
    }
98
    
99
    int *q = L->elem + i - 1;  // q指向待插入的位置
100
    int *p; 
101
    for (p = L->elem + L->length - 1; p >= q; p--)
102
    {
103
        *(p + 1) = *(p);
104
    }
105
    // 腾出位置后，在q位置插入元素e
106
    *q = e;
107
    // 插入元素后，长度别忘记加啦~ 
108
    L->length++;
109
    
110
    return 0; 
111
}
112

113
void ListTraverse_Sq(SqList *L)
114
{
115
    int i;
116
    for (i = 0; i < L->length; i++)
117
    {
118
        printf("%d ", *(L->elem + i));  // L->elem指向的是元素数组的首地址
119
    }
120
    printf("\n");
121
}
122

123
// i是从用户角度开始的（i从1开始）
124
// 如果i从0开始，我们称它从程序员角度开始的 
125
void ListDelete_Sq(SqList *L, int i, int *e)
126
{
127
    // 首先特判：判断参数的合理性
128
    if (i < 1 || i > L->length)  // 因为i最后需要减1（按照用户的角度，i是1开始的） 
129
        return;
130
    
131
    // 注意，不能这样写，因为括号内就是一个地址： int *p = &(L->elem + i - 1);
132
    int *p = L->elem + i - 1;  // 此时，p拿到的是待删除元素的地址
133
    
134
    *e = *p;
135
    
136
    int *q = L->elem + L->length - 1;
137
    
138
    // 把指向待删除目标的指针指向元素的下一位，往上移动，覆盖掉当前位。
139
    // 循环进行，直到顺序表中最后一位元素也被挪动了位置。 
140
    while(p < q)
141
    {
142
        *p = *(p + 1);  // 这里注意，需要在前面加上* 
143
        p++;
144
    }
145
    
146
    // 最后别忘记把length更新哦~
147
    L->length--; 
148
    
149
    return;
150
}
151

152

153
// 删除元素（version 2.0）：修改了其中的循环语句体，其他语句都一样 
154
// i是从用户角度开始的（i从1开始）
155
// 如果i从0开始，我们称它从程序员角度开始的 
156
void ListDelete_Sq_v2(SqList *L, int i, int *e)
157
{
158
    // 首先特判：判断参数的合理性
159
    if (i < 1 || i > L->length)  // 因为i最后需要减1（按照用户的角度，i是1开始的） 
160
        return;
161
    
162
    // 注意，不能这样写，因为括号内就是一个地址： int *p = &(L->elem + i - 1);
163
    int *p = L->elem + i - 1;  // 此时，p拿到的是待删除元素的地址
164
    
165
    *e = *p;
166
    
167
    int *q = L->elem + L->length - 1;
168
    
169
    // 把指向待删除目标的指针指向元素的下一位，往上移动，覆盖掉当前位。
170
    // 循环进行，直到顺序表中最后一位元素也被挪动了位置。 
171
    
172
    for (p++; p <= q; p++)
173
    {
174
        *(p - 1) = *p;
175
    }
176
    
177
    // 最后别忘记把length更新哦~
178
    L->length--; 
179
    
180
    return;
181
}
182

183
// 获取固定位置的元素
184
void ListGetElem_Sq(SqList *L, int i, int *e)
185
{
186
    // 特判：i
187
    if (i < 1 || i > L->length)
188
        return;
189
        
190
    // 或者可以使用 *e = L->elem[i-1]; 
191
    *e = *(L->elem + i - 1);
192
     
193
    return;
194
} 
195

196
// 获取某元素的第一次出现的位置，没有就返回-1 
197
void ListGetPos_Sq(SqList *L, int *p, int e)
198
{
199
    int i;
200
    for (i = 1; i <= L->length; i++)
201
    {
202
        if (L->elem[i - 1] == e)
203
        {
204
            *p = i;
205
            return;
206
        }
207
    }
208
    
209
    *p = -1;
210
     
211
    return;
212
} 
213

214
int main()
215
{
216
    SqList Lc;  // 操作符为 "." 
217
    Init_SqList03(&Lc);
218
    
219
    printf("Lc.length=%d, Lc.listsize=%d\n", Lc.length, Lc.listsize);
220
    
221
    ListInsert_Sq(&Lc, 1, 30);
222
    printf("Lc.length=%d, Lc.listsize=%d\n", Lc.length, Lc.listsize);
223
    ListTraverse_Sq(&Lc);
224
    
225
    
226
    ListInsert_Sq(&Lc, 1, 40);
227
    printf("Lc.length=%d, Lc.listsize=%d\n", Lc.length, Lc.listsize);
228
    ListTraverse_Sq(&Lc);
229
    
230
    ListInsert_Sq(&Lc, 1, 20);
231
    printf("Lc.length=%d, Lc.listsize=%d\n", Lc.length, Lc.listsize);
232
    ListTraverse_Sq(&Lc);
233
    
234
    ListInsert_Sq(&Lc, 1, 50);
235
    printf("Lc.length=%d, Lc.listsize=%d\n", Lc.length, Lc.listsize);
236
    ListTraverse_Sq(&Lc);
237
    
238
    printf("---------------\n"); 
239
    
240
    // 测试：删除目标位置的一个元素 
241
    int elemDel;
242
    int posDel = 2;
243
    ListDelete_Sq_v2(&Lc, posDel, &elemDel);  // 删除掉第2个元素 
244
    printf("The elem on Delete position(%d-th) is %d.\n", posDel, elemDel);
245
    printf("---------------\n");
246
    
247
    ListTraverse_Sq(&Lc);
248
    // 测试：获取目标位置的元素 
249
    int targetE;
250
    int posWant = 3;
251
    ListGetElem_Sq(&Lc, posWant, &targetE);
252
    printf("The elem on Wanted position(%d-th) is %d.\n", posWant, targetE);
253
    
254
    ListTraverse_Sq(&Lc);
255
    
256
    // 测试：获取某元素的第一次出现的位置，没有就返回-1 
257
    int posElem;
258
    int someElem = 40;
259
    ListGetPos_Sq(&Lc, &posElem, someElem);
260
    printf("The position of the someElem(%d) is %d.\n", someElem, posElem);
261
    
262
    return 0; 
263
}

运行结果


xxxxxxxxxx
20
1
Lc.length=0, Lc.listsize=100
2
Lc.length=1, Lc.listsize=100
3
30
4
Lc.length=2, Lc.listsize=100
5
40 30
6
Lc.length=3, Lc.listsize=100
7
20 40 30
8
Lc.length=4, Lc.listsize=100
9
50 20 40 30
10
---------------
11
The elem on Delete position(2-th) is 20.
12
---------------
13
50 40 30
14
The elem on Wanted position(3-th) is 30.
15
50 40 30
16
The position of the someElem(40) is 2.
17

18
--------------------------------
19
Process exited after 0.02057 seconds with return value 0
20
请按任意键继续. . .

代码整体解释

ok, 小例子结束，聊聊整个代码的具体情况。
至此（Coding005, Coding006, Coding007）基本上把顺序表中涉及的全部基础功能都已实现了。
本部分的重点是根据元素获取位置，或者根据位置操作元素（已在文章最开始进行了阐述）。为了方便测试，所以把前面的Coding005，Coding006的代码都保留了下来。如果回顾复习的时候，可以按照编号顺序，一个一个啃。很快就能吃掉这个顺序表啦~

[Coding007] DataStructure 顺序表中元素的删除

标题：顺序表的基本操作与元素的删除（C语言版）

Demo代码（加上了前面2次的代码 · 完整版）

运行结果

代码整体解释

[Coding007] DataStructure
顺序表中元素的删除